Search Results

Documents authored by Friedman, Roy

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.34
Sketching the Path to Efficiency: Lightweight Learned Cache Replacement

Authors: Rana Shahout and Roy Friedman

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Cache management policies are responsible for selecting the items that should be kept in the cache, and are therefore a fundamental design choice for obtaining an effective caching solution. Heuristic approaches have been used to identify access patterns that affect cache management decisions. However, their behavior is inconsistent, as they can perform well for certain access patterns and poorly for others. Given machine learning’s (ML) remarkable achievements in predicting diverse problems, ML techniques can be applied to create a cache management policy. Yet a significant challenge arises from the memory overhead associated with ML components. These components retain per item information and must be invoked on each access, contradicting the goal of minimizing the cache’s resource signature. In this work, we propose ALPS, a light-weight cache management policy that takes into account the cost of the ML component. ALPS combines ML with traditional heuristic-based approaches and facilitates learning by identifying several statistical features derived from space-efficient sketches. ALPS’s ML process derives its features from these sketches, resulting in a lightweight and highly effective meta-policy for cache management. We evaluate our approach over real-world workloads run against five popular heuristic cache management policies as well as a state-of-the-art ML-based policy. In our experiments, ALPS always obtained the best hit ratio. Specifically, ALPS improves the hit ratio compared to LRU by up to 20%, Hyperbolic by up to 31%, ARC by up to 9% and W-TinyLFU by up to 26% on various real-world workloads. Its resource requirements are orders of magnitude lower than previous ML-based approaches.
Cite as

Rana Shahout and Roy Friedman. Sketching the Path to Efficiency: Lightweight Learned Cache Replacement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shahout_et_al:LIPIcs.OPODIS.2023.34,
  author =	{Shahout, Rana and Friedman, Roy},
  title =	{{Sketching the Path to Efficiency: Lightweight Learned Cache Replacement}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.34},
  URN =		{urn:nbn:de:0030-drops-195249},
  doi =		{10.4230/LIPIcs.OPODIS.2023.34},
  annote =	{Keywords: Data streams, Memory Management, Cache Policy, ML}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.50
Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue

Authors: Dolev Adas and Roy Friedman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
In applications such as sharded data processing systems, data flow programming and load sharing applications, multiple concurrent data producers are feeding requests into the same data consumer. This can be naturally realized through concurrent queues, where each consumer pulls its tasks from its dedicated queue. For scalability, wait-free queues are often preferred over lock based structures. The vast majority of wait-free queue implementations, and even lock-free ones, support the multi-producer multi-consumer model. Yet, this comes at a premium, since implementing wait-free multi-producer multi-consumer queues requires utilizing complex helper data structures. The latter increases the memory consumption of such queues and limits their performance and scalability. Additionally, many such designs employ (hardware) cache unfriendly memory access patterns. In this work we study the implementation of wait-free multi-producer single-consumer queues. Specifically, we propose Jiffy, an efficient memory frugal novel wait-free multi-producer single-consumer queue and formally prove its correctness. We then compare the performance and memory requirements of Jiffy with other state of the art lock-free and wait-free queues. We show that indeed Jiffy can maintain good performance with up to 128 threads, delivers better throughput than other constructions we compared against, and consumes less memory.
Cite as

Dolev Adas and Roy Friedman. Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 50:1-50:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{adas_et_al:LIPIcs.DISC.2020.50,
  author =	{Adas, Dolev and Friedman, Roy},
  title =	{{Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{50:1--50:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.50},
  URN =		{urn:nbn:de:0030-drops-131287},
  doi =		{10.4230/LIPIcs.DISC.2020.50},
  annote =	{Keywords: Wait-freedom, MPSC Queues, Concurrent data-structures}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2019
LIPIcs, Vol. 153, OPODIS 2019, Complete Volume

Authors: Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
LIPIcs, Vol. 153, OPODIS 2019, Complete Volume
Cite as

23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 1-564, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{felber_et_al:LIPIcs.OPODIS.2019,
  title =	{{LIPIcs, Vol. 153, OPODIS 2019, Complete Volume}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{1--564},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019},
  URN =		{urn:nbn:de:0030-drops-119510},
  doi =		{10.4230/LIPIcs.OPODIS.2019},
  annote =	{Keywords: LIPIcs, Vol. 153, OPODIS 2019, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{felber_et_al:LIPIcs.OPODIS.2019.0,
  author =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{0:i--0:xxii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.0},
  URN =		{urn:nbn:de:0030-drops-117869},
  doi =		{10.4230/LIPIcs.OPODIS.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.34
Give Me Some Slack: Efficient Network Measurements

Authors: Ran Ben Basat, Gil Einziger, and Roy Friedman

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log (W/epsilon)) lower bound for RW epsilon additive approximations and a Omega(log (W/epsilon)+log log R) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^(-1) log(RW)log log (RW)) space and performs updates in O(log (RW)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.
Cite as

Ran Ben Basat, Gil Einziger, and Roy Friedman. Give Me Some Slack: Efficient Network Measurements. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.MFCS.2018.34,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy},
  title =	{{Give Me Some Slack: Efficient Network Measurements}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.34},
  URN =		{urn:nbn:de:0030-drops-96165},
  doi =		{10.4230/LIPIcs.MFCS.2018.34},
  annote =	{Keywords: Streaming, Network Measurements, Statistics, Lower Bounds}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.163
Brief Announcement: Give Me Some Slack: Efficient Network Measurements

Authors: Ran Ben Basat, Gil Einziger, and Roy Friedman

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of our paper [{Ben Basat} et al., 2017] is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log{R}) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log ({W/epsilon})) lower bound for RW epsilon additive approximations and a Omega(log ({W/epsilon})+log log{R}) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^{-1} log ({RW})log log ({RW})) space and performs updates in O(log ({RW})) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.
Cite as

Ran Ben Basat, Gil Einziger, and Roy Friedman. Brief Announcement: Give Me Some Slack: Efficient Network Measurements. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 163:1-163:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ICALP.2018.163,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy},
  title =	{{Brief Announcement: Give Me Some Slack: Efficient Network Measurements}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{163:1--163:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.163},
  URN =		{urn:nbn:de:0030-drops-91672},
  doi =		{10.4230/LIPIcs.ICALP.2018.163},
  annote =	{Keywords: Streaming, Algorithms, Sliding window, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.27
Hardening Cassandra Against Byzantine Failures

Authors: Roy Friedman and Roni Licher

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Cassandra is one of the most widely used distributed data stores. In this work, we analyze Cassandra’s vulnerabilities when facing Byzantine failures and propose protocols for hardening Cassandra against them. We examine several alternative design choices and compare between them both qualitatively and empirically by using the Yahoo! Cloud Serving Benchmark (YCSB) performance benchmark. Some of our proposals include novel combinations of quorum access protocols with MAC signatures arrays and elliptic curve public key cryptography so that in the normal data path, there are no public key verifications and only a single relatively cheap elliptic curve signature made by the client. Yet, these enable data recovery and authentication despite Byzantine failures and across membership configuration changes. In the experiments, we demonstrate that our best design alternative obtains roughly half the performance of plain (non-Byzantine) Cassandra.
Cite as

Roy Friedman and Roni Licher. Hardening Cassandra Against Byzantine Failures. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{friedman_et_al:LIPIcs.OPODIS.2017.27,
  author =	{Friedman, Roy and Licher, Roni},
  title =	{{Hardening Cassandra Against Byzantine Failures}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.27},
  URN =		{urn:nbn:de:0030-drops-86429},
  doi =		{10.4230/LIPIcs.OPODIS.2017.27},
  annote =	{Keywords: Cassandra, Byzantine Fault Tolerance, Distributed Storage}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.11
Efficient Summing over Sliding Windows

Authors: Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of Omega(1/epsilon + log(W)) memory bits for Wepsilon-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/epsilon + log(W)) bits, indicating that the algorithm is optimal and that the bound is tight. Next, the more general problem of maintaining a sum of the last W integers, each in the range of {0, 1, ..., R}, is addressed. The paper shows that approximating the sum within an additive error of RW epsilon can also be done using Theta(1/epsilon + log(W)) bits for epsilon = Omega(1/W). For epsilon = o(1/W), we present a succinct algorithm which uses B(1 + o(1)) bits, where B = Theta(W*log(1/(W*epsilon))) is the derived lower bound. We show that all lower bounds generalize to randomized algorithms as well. All algorithms process new elements and answer queries in O(1) worst-case time.
Cite as

Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient Summing over Sliding Windows. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.SWAT.2016.11,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy and Kassner, Yaron},
  title =	{{Efficient Summing over Sliding Windows}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.11},
  URN =		{urn:nbn:de:0030-drops-60241},
  doi =		{10.4230/LIPIcs.SWAT.2016.11},
  annote =	{Keywords: Streaming, Statistics, Lower Bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact